home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / pcr / pcr4_4.lha / DIST / threads / ThreadsQueues.c < prev    next >
C/C++ Source or Header  |  1992-02-18  |  13KB  |  598 lines
  1. /* begincopyright
  2.   Copyright (c) 1988 Xerox Corporation. All rights reserved.
  3.   Use and copying of this software and preparation of derivative works based
  4.   upon this software are permitted. Any distribution of this software or
  5.   derivative works must comply with all applicable United States export
  6.   control laws. This software is made available AS IS, and Xerox Corporation
  7.   makes no warranty about the software, its performance or its conformity to
  8.   any specification. Any person obtaining a copy of this software is requested
  9.   to send their name and post office or electronic mail address to:
  10.     PCR Coordinator
  11.     Xerox PARC
  12.     3333 Coyote Hill Rd.
  13.     Palo Alto, CA
  14.   endcopyright */
  15. /*
  16.  * ThreadsQueues.c
  17.  *
  18.  * Demers, January 25, 1991 4:25:23 pm PST
  19.  * Theimer, January 25, 1991 4:25:26 pm PST
  20.  */
  21.  
  22. #include "xr/BasicTypes.h"
  23. #include "xr/Threads.h"
  24. #include "xr/ThreadsBackdoor.h"
  25. #include "xr/ThreadsPrivate.h"
  26. #include "xr/ThreadsMsgPrivate.h"
  27. #include <sys/time.h>
  28.         /* debugging only */
  29.  
  30.  
  31. #define SS1_HAT_KLUDGE    1
  32.  
  33. long XR_GetMicroseconds()
  34. {
  35.     struct timeval t;
  36.  
  37.     XR_GetTimeOfDay(&t, 0);
  38.     return(((t.tv_sec & 0x3ff) * 1000000) + t.tv_usec);
  39. }
  40.  
  41. /*
  42.  * Thread Queues
  43.  */
  44.  
  45.  
  46. void
  47. XR_AddHdTQ (tq, t)
  48.     XR_TQ tq;
  49.     XR_Thread t;
  50. {
  51.     XR_ASSERT( t->t_next == NIL, "AddHdTQ a" );
  52.     t->t_tq = tq;
  53.     if( tq->tq_tail == NIL ) {
  54.         tq->tq_tail = t->t_next = t;
  55.     } else {
  56.         XR_Thread tl = tq->tq_tail;
  57.     t->t_next = tl->t_next;
  58.     tl->t_next = t;
  59.     }
  60. }
  61.  
  62.  
  63. void
  64. XR_AddTlTQ (tq, t)
  65.     XR_TQ tq;
  66.     XR_Thread t;
  67. {
  68.     XR_ASSERT( t->t_next == NIL, "AddTlTQ b" );
  69.     t->t_tq = tq;
  70.     if( tq->tq_tail == NIL ) {
  71.         tq->tq_tail = t->t_next = t;
  72.     } else {
  73.         XR_Thread tl = tq->tq_tail;
  74.     t->t_next = tl->t_next;
  75.     tq->tq_tail = tl->t_next = t;
  76.     }
  77. }
  78.  
  79.  
  80. XR_Thread
  81. XR_RemHdTQ (tq)
  82.     XR_TQ tq;
  83. {
  84.     XR_Thread hd;
  85.     XR_ASSERT( tq->tq_tail != NIL, "RemHdPQ a" );
  86.     if( (hd = tq->tq_tail->t_next) == tq->tq_tail ) {
  87.         tq->tq_tail = NIL;
  88.     } else {
  89.         tq->tq_tail->t_next = hd->t_next;
  90.     }
  91.     hd->t_next = NIL;
  92.     hd->t_tq = NIL;
  93.     return( hd );
  94. }
  95.  
  96.  
  97. void
  98. XR_RemTQ (t)
  99.     XR_Thread t;
  100. {
  101.     XR_TQ tq;
  102.     XR_Thread each;
  103.  
  104.     if( (tq = t->t_tq) == NIL ) return;
  105.     if( (each = tq->tq_tail) == NIL ) {
  106.         XR_Panic("RemTQ 0");
  107.     }
  108.     for(;;) {
  109.         XR_Thread next = each->t_next;
  110.     if( next == t ) break;
  111.     if( next == tq->tq_tail ) return;
  112.     each = next;
  113.     }
  114.     if( each == t ) /* singleton */ {
  115.         tq->tq_tail = NIL;
  116.     } else if( t == tq->tq_tail ) /* removing tail */ {
  117.         each->t_next = tq->tq_tail = t->t_next;
  118.     } else /* removing from elsewhere */ {
  119.         each->t_next = t->t_next;
  120.     }
  121.     t->t_next = NIL;
  122.     t->t_tq = NIL;
  123. }
  124.  
  125.  
  126.  
  127. /*
  128.  * Wait Queues
  129.  */
  130.  
  131.  
  132. void
  133. XR_AddHdWQ (wq, t)
  134.     XR_WQ wq;
  135.     XR_Thread t;
  136. {
  137.     XR_ASSERT( t->t_wNext == NIL, "AddHdWQ a" );
  138.     t->t_wq = wq;
  139.     if( wq->wq_tail == NIL ) {
  140.         wq->wq_tail = t->t_wNext = t;
  141.     } else {
  142.         register XR_Thread tl = wq->wq_tail;
  143.     t->t_wNext = tl->t_wNext;
  144.     tl->t_wNext = t;
  145.     }
  146. }
  147.  
  148.  
  149. void
  150. XR_AddTlWQ (wq, t)
  151.     XR_WQ wq;
  152.     XR_Thread t;
  153. {
  154.     XR_ASSERT( t->t_wNext == NIL, "AddTlWQ a" );
  155.     t->t_wq = wq;
  156.     if( wq->wq_tail == NIL ) {
  157.         wq->wq_tail = t->t_wNext = t;
  158.     } else {
  159.         XR_Thread tl = wq->wq_tail;
  160.     t->t_wNext = tl->t_wNext;
  161.     wq->wq_tail = tl->t_wNext = t;
  162.     }
  163. }
  164.  
  165.  
  166. XR_Thread
  167. XR_RemHdWQ (wq)
  168.     XR_WQ wq;
  169. {
  170.     XR_Thread hd;
  171.     XR_ASSERT( wq->wq_tail != NIL, "RemHdWQ a" );
  172.     if( (hd = wq->wq_tail->t_wNext) == wq->wq_tail ) {
  173.         wq->wq_tail = NIL;
  174.     } else {
  175.         wq->wq_tail->t_wNext = hd->t_wNext;
  176.     }
  177.     hd->t_wNext = NIL;
  178.     hd->t_wq = NIL;
  179.     return( hd );
  180. }
  181.  
  182.  
  183. void
  184. XR_RemWQ (t)
  185.     XR_Thread t;
  186. {
  187.     XR_Thread each;
  188.     XR_WQ wq = t->t_wq;
  189.  
  190.     if( wq == NIL ) return;
  191.     if( (each = wq->wq_tail) == NIL )
  192.         XR_Panic("RemWQ 0");
  193.     for(;;) {
  194.         XR_Thread next = each->t_wNext;
  195.     if( next == t ) break;
  196.     if( next == wq->wq_tail )
  197.         XR_Panic("RemWQ 1");
  198.     each = next;
  199.     }
  200.     if( each == t ) /* singleton */ {
  201.         wq->wq_tail = NIL;
  202.     } else if( t == wq->wq_tail ) /* removing tail */ {
  203.         each->t_wNext = wq->wq_tail = t->t_wNext;
  204.     } else /* removing from elsewhere */ {
  205.         each->t_wNext = t->t_wNext;
  206.     }
  207.     t->t_wNext = NIL;
  208.     t->t_wq = NIL;
  209. }
  210.  
  211.  
  212. #if (SS1_HAT_KLUDGE)
  213. /*
  214.  * RequestResched hacks for HAT stuff on SPARCStation-1
  215.  */
  216.  
  217. unsigned XR_hatCtl = 0;
  218.  
  219. #   define XR_HATCTL_NOT_OTHER    1
  220. #   define XR_HATCTL_NOT_ALL    2
  221. #   define XR_HATCTL_NOT_SELF    4
  222. #   define XR_HATCTL_NOT_NAKED    8
  223.  
  224.  
  225. unsigned
  226. XR_GetHATCtl()
  227. {
  228.     return XR_hatCtl;
  229. }
  230.  
  231. unsigned
  232. XR_SetHATCtl(new)
  233.     unsigned new;
  234. {
  235.     unsigned old = XR_hatCtl;
  236.     XR_hatCtl = new;
  237.     return old;
  238. }
  239.  
  240. static void
  241. XR_ComplexRequestResched(vpe)
  242.     XR_VPE vpe;
  243. {
  244.     unsigned skipBits;
  245.  
  246.     if( (skipBits = XR_hatCtl) != 0 ) {
  247.         if( XR_vpe == NIL ) {
  248.             if( skipBits & XR_HATCTL_NOT_NAKED ) return;
  249.         } else if( vpe == NIL ) {
  250.             if( skipBits & XR_HATCTL_NOT_ALL ) return;
  251.             if( skipBits & XR_HATCTL_NOT_OTHER ) vpe = XR_vpe;
  252.         } else if( vpe == XR_vpe ) {
  253.             if( skipBits & XR_HATCTL_NOT_SELF ) return;
  254.         } else {
  255.             if( skipBits & XR_HATCTL_NOT_OTHER ) return;
  256.         }
  257.     }
  258.     XR_RequestResched(vpe);
  259. }
  260.  
  261. #define XR_RequestResched XR_ComplexRequestResched
  262.  
  263. #endif    /* SS1_HAT_KLUDGE */
  264.  
  265. /*
  266.  * Monitor Locks
  267.  */
  268.  
  269. void
  270. XR_InitializeMonitor (ml)
  271.     XR_ML ml;
  272. {
  273.     XR_InitWQ(&(ml->ml_wq));
  274.     ml->ml_holder = NIL;
  275. }
  276.  
  277.  
  278. void
  279. XR_MonitorEntryOutOfLine (ml)
  280.     XR_ML ml;
  281. {
  282.     for(;;) {
  283.         XR_AcquireGSL(&(ml->ml_gsl));
  284.         if( ml->ml_holder == NIL ) break;
  285.     XR_AddTlWQ(&(ml->ml_wq), XR_currThread);
  286.     XR_Switch( ml->ml_holder, XR_SSTAT_WAIT_ML, XR_SWSTAT_THREAD );
  287.     }
  288.     ml->ml_holder = XR_currThread;
  289.     XR_ReleaseGSL(&(ml->ml_gsl));
  290. }
  291.  
  292.  
  293. #if (!XR_MONITOR_ENTRY)
  294. void
  295. XR_MonitorEntry (ml)
  296.     XR_ML ml;
  297. {
  298.     if( XR_TryGSL(&(ml->ml_gsl)) ) {
  299.         if( ml->ml_holder == NIL ) {
  300.             ml->ml_holder = XR_currThread;
  301.             XR_ReleaseGSL(&(ml->ml_gsl));
  302.             return;
  303.         }
  304.         XR_ReleaseGSL(&(ml->ml_gsl));
  305.     }
  306.     XR_MonitorEntryOutOfLine (ml);
  307. }
  308. #endif
  309.  
  310.  
  311. void
  312. XR_MonitorExitOutOfLine (ml)
  313.     XR_ML ml;
  314. {
  315.     XR_VPE chosenVPE = NIL;
  316.     XR_Thread chosenThread = NIL;
  317.     XR_VPE vpeToReschedOnMonitorExit;
  318.  
  319.     vpeToReschedOnMonitorExit =
  320.             (XR_VPE)(XR_currThread->t_vpeToReschedOnMonitorExit);
  321.     XR_currThread->t_vpeToReschedOnMonitorExit = NIL;
  322.  
  323.     XR_AcquireGSL(&(ml->ml_gsl));
  324.     if( XR_NonemptyWQ(&(ml->ml_wq)) )
  325.         chosenThread = XR_RemHdWQ(&(ml->ml_wq));
  326.     ml->ml_holder = NIL;
  327.     XR_ReleaseGSL(&(ml->ml_gsl));
  328.     
  329.     if (chosenThread != NIL) {
  330.         chosenVPE = XR_SetThreadReady(chosenThread);
  331.     }
  332.     
  333.     if( chosenVPE == NIL ) {
  334.         chosenVPE = vpeToReschedOnMonitorExit;
  335.     } else /* chosenVPE != NIL */ {
  336.         if( (vpeToReschedOnMonitorExit != NIL)
  337.                 && (vpeToReschedOnMonitorExit != chosenVPE) )
  338.             chosenVPE = DEFERRED_RESCHED_ALL;
  339.     }
  340.     if( chosenVPE != NIL ) {
  341.         if( chosenVPE == XR_vpe ) {
  342.             XR_Switch(NIL, XR_SSTAT_READY, XR_SWSTAT_THREAD);
  343.         } else {
  344.             XR_RequestResched(
  345.                 (chosenVPE == DEFERRED_RESCHED_ALL) ? NIL : chosenVPE
  346.             );
  347.             /* We held the metalock for a little while */
  348.             XR_CheckReschedRequest();
  349.         }
  350.     } else {
  351.         XR_CheckReschedRequest();
  352.     }
  353. }
  354.  
  355.  
  356. #if (!XR_MONITOR_EXIT)
  357. void
  358. XR_MonitorExit (ml)
  359.     XR_ML ml;
  360. {
  361.     XR_VPE vpeToReschedOnMonitorExit
  362.             = (XR_VPE)(XR_currThread->t_vpeToReschedOnMonitorExit);
  363.  
  364.     if( XR_TryGSL(&(ml->ml_gsl)) ) {
  365.         if( (! XR_NonemptyWQ(&(ml->ml_wq)))
  366.                 && (vpeToReschedOnMonitorExit == NIL) ) {
  367.             ml->ml_holder = NIL;
  368.             XR_ReleaseGSL(&(ml->ml_gsl));
  369.             return;
  370.         }
  371.         XR_ReleaseGSL(&(ml->ml_gsl));
  372.     }
  373.     XR_MonitorExitOutOfLine (ml);
  374. }
  375. #endif
  376.  
  377.  
  378. /*
  379.  * Condition Variables
  380.  */
  381.  
  382.  
  383. void
  384. XR_InitializeCondition (cv, timeout)
  385.     XR_CV cv;
  386.     XR_Ticks timeout;
  387. {
  388.     XR_InitWQ(&(cv->cv_wq));
  389.     cv->cv_timeout = timeout;
  390.     cv->cv_abortable = FALSE;
  391.     cv->cv_wakeupWaiting = FALSE;
  392. }
  393.     
  394.  
  395. int
  396. XR_WaitCV (cv, ml)
  397.     XR_CV cv;
  398.     XR_ML ml;
  399. {
  400.     XR_currThread->t_abortable = cv->cv_abortable;
  401.     XR_AcquireGSL(&(cv->cv_gsl));
  402.     if( cv->cv_wakeupWaiting ) {
  403.         cv->cv_wakeupWaiting = FALSE;
  404.         XR_ReleaseGSL(&(cv->cv_gsl));
  405.     } else {
  406.         if( ml != NIL ) {
  407.             XR_MonitorExit (ml);
  408.             XR_currThread->t_mlNeeded = ml;
  409.         }
  410.         XR_AddTlWQ(&(cv->cv_wq), XR_currThread);
  411.         XR_Switch(NIL, XR_SSTAT_WAIT_CV, XR_SWSTAT_THREAD);
  412.         if( ml != NIL ) {
  413.             XR_MonitorEntry (ml);
  414.             XR_currThread->t_mlNeeded = NIL;
  415.         }
  416.     }
  417.     if( XR_currThread->t_abortRequest && XR_currThread->t_abortable ) {
  418.         XR_currThread->t_abortRequest = FALSE;
  419.     return(-1);
  420.     }
  421.     return(0);
  422. }
  423.  
  424.  
  425.  
  426. /*
  427.  * Notify, Broadcast and NakedNotify must be careful to avoid smashes
  428.  *   in the case where the condition is allocated on the
  429.  *   notify-ee's local frame.
  430.  *
  431.  * ajd+chh July 16, 1990 2:29:12 pm PDT
  432.  */
  433.  
  434.  
  435. void
  436. XR_Notify (cv)
  437.     XR_CV cv;
  438. {
  439.     XR_VPE chosenVPE;
  440.     XR_Thread chosenThread;
  441.     XR_ML mlNeeded;
  442.  
  443.     XR_AcquireGSL(&(cv->cv_gsl));
  444.     if( XR_NonemptyWQ(&(cv->cv_wq)) ) {
  445.         chosenThread = XR_RemHdWQ(&(cv->cv_wq));
  446.     } else {
  447.         chosenThread = NIL;
  448.     }
  449.     XR_ReleaseGSL(&(cv->cv_gsl));
  450.     if( chosenThread != NIL ) {
  451.         /* defer resched if we're holding lock needed by chosenThread mmt+ajd */
  452.         chosenVPE = XR_SetThreadReady( chosenThread );
  453.         if( ((mlNeeded = chosenThread->t_mlNeeded) != NIL)
  454.                 && (mlNeeded->ml_holder == XR_currThread) ) {
  455.             XR_currThread->t_vpeToReschedOnMonitorExit = chosenVPE;
  456.             XR_CheckReschedRequest();
  457.         } else {
  458.             if( chosenVPE == XR_vpe ) {
  459.                 XR_Switch(NIL, XR_SSTAT_READY, XR_SWSTAT_THREAD);
  460.             } else if( chosenVPE != NIL ) {
  461.                 XR_RequestResched(chosenVPE);
  462.                 XR_CheckReschedRequest();
  463.             }
  464.         }
  465.     }
  466. }
  467.  
  468.  
  469.  
  470.  
  471. #define XR_BCAST_LIST_ENTRIES    15
  472.  
  473. typedef struct XR_BcastTListRep {
  474.     struct XR_BcastTListRep *bctl_prev;
  475.     XR_Thread bctl_t[XR_BCAST_LIST_ENTRIES];
  476. } * XR_BcastTList;
  477.  
  478.  
  479. static void
  480. XR_BroadcastInner (cv, otherNotifyees)
  481.     XR_CV cv;
  482.     XR_BcastTList otherNotifyees;
  483. {
  484.     int i = 0;
  485.     struct XR_BcastTListRep bctl;
  486.     XR_BcastTList bctlp;
  487.     XR_VPE chosenVPE = NIL;
  488.     int numChosen = 0;
  489.     XR_VPE tvpe;
  490.     bool canDefer;
  491.  
  492.     if( otherNotifyees == NIL ) XR_AcquireGSL(&(cv->cv_gsl));
  493.  
  494.         bctl.bctl_prev = otherNotifyees;
  495.  
  496.         while( XR_NonemptyWQ(&(cv->cv_wq)) ) {
  497.             if( i >= XR_BCAST_LIST_ENTRIES ) {
  498.                 XR_BroadcastInner(cv, &bctl);
  499.                 return;
  500.             }
  501.             bctl.bctl_t[i] = XR_RemHdWQ(&(cv->cv_wq));
  502.             i++;
  503.         }
  504.  
  505.     XR_ReleaseGSL(&(cv->cv_gsl));
  506.  
  507.     canDefer = TRUE;
  508.     bctlp = &bctl;
  509.     while( bctlp != NIL ) {
  510.         if( i == 0 ) {
  511.             bctlp = bctlp->bctl_prev;
  512.             i = XR_BCAST_LIST_ENTRIES;
  513.         } else {
  514.             XR_Thread chosenThread;
  515.             XR_ML mlNeeded;
  516.             i--;
  517.             chosenThread = bctlp->bctl_t[i];
  518.             tvpe = XR_SetThreadReady( chosenThread );
  519.             if( tvpe != NIL ) {
  520.                 /* see if this thread inhibits resched deferral mmt+ajd */
  521.                 if( ((mlNeeded = chosenThread->t_mlNeeded) == NIL)
  522.                         || (mlNeeded->ml_holder != XR_currThread) ) {
  523.                     canDefer = FALSE;
  524.                 }
  525.                 numChosen++; chosenVPE = tvpe;
  526.             }
  527.         }
  528.     }
  529.     if( numChosen == 0 ) {
  530.         return;
  531.     } else if( numChosen > 1 ) {
  532.         if( canDefer )
  533.             XR_currThread->t_vpeToReschedOnMonitorExit = DEFERRED_RESCHED_ALL;
  534.         else
  535.             XR_RequestResched(NIL);
  536.     } else /* numChosen == 1 */ {
  537.         if( canDefer ) {
  538.             XR_currThread->t_vpeToReschedOnMonitorExit = chosenVPE;
  539.         } else /* (!canDefer) */ {
  540.             if( chosenVPE == XR_vpe ) {
  541.                 XR_Switch(NIL, XR_SSTAT_READY, XR_SWSTAT_THREAD);
  542.             } else if( chosenVPE != NIL ) {
  543.                 XR_RequestResched(chosenVPE);
  544.             }
  545.         }
  546.     }
  547.     /* XR_SetThreadReady held the metalock */
  548.     XR_CheckReschedRequest();
  549. }
  550.  
  551. void
  552. XR_Broadcast (cv)
  553.     XR_CV cv;
  554. {
  555.     XR_BroadcastInner(cv, NIL);
  556. }
  557.  
  558.  
  559.  
  560. XR_VPE
  561. XR_NakedNotifyInner (icv)
  562.     XR_CV icv;
  563. {
  564.     XR_Thread chosenThread;
  565.     XR_VPE chosenVPE = NIL;
  566.  
  567.     /* acquire gsl protecting monitor using psl op! */
  568.         XR_AcquirePSL(((XR_PSL)(&(icv->cv_gsl))));
  569.  
  570.     if( XR_NonemptyWQ(&(icv->cv_wq)) ) {
  571.         chosenThread = XR_RemHdWQ(&(icv->cv_wq));
  572.     } else {
  573.         icv->cv_wakeupWaiting = TRUE;
  574.         chosenThread = NIL;
  575.     }
  576.  
  577.     /* release gsl protecting monitor using psl op! */
  578.         XR_ReleasePSL(((XR_PSL)(&(icv->cv_gsl))));
  579.  
  580.     if( chosenThread != NIL ) {
  581.         chosenVPE = XR_SetThreadReady( chosenThread );
  582.         if(XR_vpe != NIL) XR_CheckReschedRequest();
  583.     }
  584.     return chosenVPE;
  585. }
  586.  
  587.  
  588. void
  589. XR_NakedNotify (icv)
  590.     XR_CV icv;
  591. {
  592.     XR_VPE chosenVPE;
  593.  
  594.     if( (chosenVPE = XR_NakedNotifyInner(icv)) != NIL )
  595.         XR_RequestResched(chosenVPE);
  596. }
  597.  
  598.